package org.niu.tree;

import java.util.*;

public class RTree {
    List<TreeNode> list = new ArrayList<>();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = reConstructBinaryTree(xianxu,zhongxu);
        bfs(root);
        int[] ans = new int[list.size()+1];
        for(int i = 0;i < list.size();i++){
            ans[i] = list.get(i).val;
        }
        return ans;
    }
    void bfs(TreeNode root){
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()){
            int size = q.size();
            for (int i = 0; i < size;i++){
                TreeNode p = q.poll();
                if(i == size-1){
                    list.add(p);
                }
                if(p.left!=null) q.add(p.left);
                if(p.right!=null) q.add(p.right);
            }
        }
    }
    private TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;

            }
        }

        return node;
    }
}
